#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> hashTable;//<num, index> 
        vector<int> res;

        /*=================================================
        for i  遍历nums元素
            elmt = target - nums[i]
            hashtable 里去找elmt
            如果 found 
                返回 it->second, i 
            如果没找到
                把当前元素放入hashTable; {nums[i], i}
        ================================================= */
        for (int i= 0; i < nums.size(); i++) {
            auto it = hashTable.find(target - nums[i]); 
            if (it != hashTable.end() && it->second != i) {
                res.push_back(it->second);
                res.push_back(i);
            } else {
                hashTable[nums[i]] = i;
            }
        }
        return res;
    }
};

void test(vector<int> &arr, int target) {
     Solution* sln = new Solution;
     vector<int> res = sln->twoSum(arr, target);
     for (auto j : res) {
         std::cout<< j << " "; 
     }
     std::cout<< std::endl; 
}

int main()
{
    vector<int> arr = {1,3,4,9};
    int target = 13;
    test(arr, target);
    return 0;
}
